package graph;

import java.util.HashMap;
import java.util.Map;

/**
 * Dijkstra（迪杰斯特拉算法）使用二叉堆优化的版本
 * 算法时间复杂度为 O(n^logn)
 */
public class DijkstraGood_1122 {
    /**
     * 获取源点到图中任意点的最短距离
     * @param node 源点
     */
    public static Map<Node<Integer>, Integer> dijkstra(Node<Integer> node) {
        // 存储源点到任意节点的最短距离
        Map<Node<Integer>, Integer> ans = new HashMap<>();
        NodeHeap<Integer> heap = new NodeHeap<>();
        heap.push(node, 0);
        while (!heap.isEmpty()) {
            // 每次弹出未确定最短距离且距离源点最近的点
            NodeHeap.NodeWithWeight<Integer> nodeWithWeight = heap.pop();
            // 对相邻的边进行松弛
            for (Edge<Integer> nextEdge : nodeWithWeight.getNode().nextEdges) {
                heap.push(nextEdge.to, nextEdge.weight + nodeWithWeight.getWeight());
            }
            ans.put(nodeWithWeight.getNode(), nodeWithWeight.getWeight());
        }
        return ans;
    }

}
